package top.hkyzf.study.leetcode.graph;

import org.junit.Test;

import java.util.Arrays;

/**
 * @author 朱峰
 * @date 2022-2-14 10:19
 */
public class 飞地的数量_1020 {
    boolean mark = false;

    public int numEnclaves(int[][] grid) {
        int result = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == 1) {
                    int dfs = dfs(grid, i, j);
                    if (!mark) {
                        result += dfs;
                    } else {
                        mark = false;
                    }
                }
            }
        }
        return result;
    }

    private int dfs(int[][] grid, int i, int j) {
        int[] dX = {-1,0,1,0};
        int[] dY = {0,-1,0,1};
        int ans = 0;
        grid[i][j] = 0;
        ans++;
        for (int k = 0; k < 4; k++) {
            int newX = i + dX[k];
            int newY = j + dY[k];
            if (newX >= 0 && newY >= 0 && newX < grid.length && newY < grid[0].length) {
                if (grid[newX][newY] == 1) {
                    ans += dfs(grid, newX, newY);
                }
            } else {
                // 界外
                mark = true;
            }
        }
        return ans;
    }

    @Test
    public void testNumEnclaves () {
        int[][] grid = {{0,1,1,0},{0,0,1,0},{0,0,1,0},{0,0,0,0}};
        for (int[] g : grid) {
            System.out.println(Arrays.toString(g));
        }
        System.out.println(numEnclaves(grid));
    }
}
